package doujian.match;

import java.io.StringWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;

import org.json.simple.JSONArray;
import org.json.simple.JSONObject;
import org.json.simple.parser.JSONParser;
import org.json.simple.parser.ParseException;

import com.google.gson.Gson;
import com.google.gson.reflect.TypeToken;

import edu.princeton.cs.algs4.BipartiteMatching;
import edu.princeton.cs.algs4.BipartiteX;
import edu.princeton.cs.algs4.Graph;

/**
 * 最优匹配入口
 * Created by Administrator on 2017/4/16.
 */
public class Match {
	
	/**
	 * 根据原始数据，去除单边连接
	 * @param stuList
	 * @param hostList
	 * @return
	 */
//	stuList
//	[
//	  {
//	    "id": 1,
//	    "selections": [ 4, 5]
//	  },
//	  {
//	    "id": 2,
//	    "selections": [ 5 ]
//	  },
//	  {
//	    "id": 3,
//	    "selections": [ 4, 5 ]
//	  }
//	]
	
//	hostList
//	[
//	  {
//	    "id": 4,
//	    "selections": [ 1 ]
//	  },
//	  {
//	    "id": 5,
//	    "selections": [ 1, 2 ]
//	  }
//	]
	public static String removeOneWayEdge(String stuList, String hostList) throws Exception{
        Gson gson = new Gson();

        //房东端json -> list
        List<MatchModel> hList =gson.fromJson(hostList, new TypeToken<List<MatchModel>>(){}.getType());
        
        //学生端json -> list        
        List<MatchModel> sList =gson.fromJson(stuList, new TypeToken<List<MatchModel>>(){}.getType());
        HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        for(MatchModel stu: sList){
        	map.put(stu.id, stu.selections);
        }

        //去除单边
        ArrayList<MatchModel> result = new ArrayList<MatchModel>();
        for(int i=0;i<hList.size();i++){
        	MatchModel host = hList.get(i);
        	MatchModel model = new MatchModel();
        	model.id =  host.id;
        	for(int j=0;j<host.selections.size();j++){
        		int stuId = host.selections.get(j);
        		if(map.get(stuId)!= null && map.get(stuId).contains(model.id)){
        			model.selections.add(stuId);
        		}
        	}
        	if(!model.selections.isEmpty()){
        		result.add(model);
        	}
        }
		return gson.toJson(result);
	}

    /**
     * 获取最优匹配结果
     *
     * @param json
     * @return
     */
    public static String allocate(String json) throws ParseException, Exception {
        //Parsing JSON
        JSONParser parser = new JSONParser();
        JSONArray selections = (JSONArray) parser.parse(json);
        Map<Integer, Integer> nodes = new HashMap();
        Map<Integer, List<Integer>> adjList = new HashMap();
        for (Object obj : selections) {
            JSONObject selection = (JSONObject) obj;
            int host_id = Math.toIntExact((long) selection.get("id"));
            nodes.put(host_id, nodes.size());
            List<Integer> neighbours = new ArrayList();
            JSONArray tenants = (JSONArray) selection.get("selections");
            for (Object tobj : tenants) {
                int tenant_id = Math.toIntExact((long) tobj);
                if (!nodes.containsKey(tenant_id)) {
                    nodes.put(tenant_id, nodes.size());
                }
                neighbours.add(tenant_id);
            }
            adjList.put(host_id, neighbours);
        }

        Graph g = new Graph(nodes.size());
        
        //Create edges
        for (Integer host_id : adjList.keySet()) {
            int host_node = nodes.get(host_id);
//            System.out.println(host_node+"; ");
            for (Integer tenant_id : adjList.get(host_id)) {
                int tenant_node = nodes.get(tenant_id);
                g.addEdge(host_node, tenant_node);
//                System.out.print("\t"+tenant_node+" ");
            }
//            System.out.println();
        }
        
        ;
        
        BipartiteX bipartition = new BipartiteX(g);
        if (!bipartition.isBipartite()) {
            throw new Exception("The data in the input JSON is invalid. The cause is that a host selects itself.");
        }

        //Compute matching and generate results
        BipartiteMatching matching = new BipartiteMatching(g);
        JSONArray output = new JSONArray();
        for (Integer host_id : adjList.keySet()) {
            JSONObject match = new JSONObject();
            match.put("host_id", host_id);
            JSONArray tenants = new JSONArray();
            int host_node = nodes.get(host_id);
            for (Integer tenant_id : adjList.get(host_id)) {
                int tenant_node = nodes.get(tenant_id);
                if (matching.mate(host_node) == tenant_node) {
                    tenants.add(tenant_id);
                }
            }
            match.put("tenants", tenants);
            output.add(match);
        }

        return output.toJSONString();
    }
}
